#include<stdio.h>
#include<queue>
using namespace std;
const int MAX = 30004;
const int INF = 99999999;
struct edge
{
int u,v,w;
edge *next;
}* head[MAX];
int dist[MAX],vn;
int stack[MAX];
void add_edge(int u,int v,int w)
{
edge *ptr = new edge;
ptr->v = v;
ptr->w = w;
ptr->next = head[u];
head[u] = ptr;
}
void init(void)
{
int i;
for(i=0;i<MAX;i++)
   head[i] = NULL;
}
void SPFA(int source,int vn)
{
bool inq[MAX];
int i;
for(i=0;i<=vn;i++)
{
   inq[i] = false;
   dist[i] = INF;
}
int stack[MAX],top = 0;
inq[source] = true;
dist[source] = 0;
stack[top++] = source;
while(top)
{
   int t = stack[--top];
   inq[t] = false;
   edge *p;
   for(p = head[t];p;p=p->next)
   {
    if(dist[p->v] > dist[t] + p->w)
    {
     dist[p->v] = dist[t] + p->w;
     if(!inq[p->v])
     {
      inq[p->v] = true;
      stack[top++]=p->v;
     }
    }
   }
}
}
int main()
{
int n,m,t;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
int i;
vn = n;
init();
for(i=0;i<m;i++)
{
   int a,b,c;
   scanf("%d%d%d",&a,&b,&c);
   add_edge(a,b,c);
}
SPFA(1,vn);
printf("%d\n",dist[vn]);
}
return 0;
}
